{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Unreachable Pairs of Nodes in an Undirected Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计无向图中无法互相到达点对数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;，表示一张<strong>&nbsp;无向图</strong>&nbsp;中有 <code>n</code>&nbsp;个节点，编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。同时给你一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示节点&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条&nbsp;<strong>无向</strong>&nbsp;边。</p>\n",
    "\n",
    "<p>请你返回 <strong>无法互相到达</strong>&nbsp;的不同 <strong>点对数目</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/05/05/tc-3.png\" style=\"width: 267px; height: 169px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 3, edges = [[0,1],[0,2],[1,2]]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/05/05/tc-2.png\" style=\"width: 295px; height: 269px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]\n",
    "<b>输出：</b>14\n",
    "<b>解释：</b>总共有 14 个点对互相无法到达：\n",
    "[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]\n",
    "所以我们返回 14 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li>不会有重复边。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-unreachable-pairs-of-nodes-in-an-undirected-graph](https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-unreachable-pairs-of-nodes-in-an-undirected-graph](https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[0,1],[0,2],[1,2]]', '7\\n[[0,2],[0,5],[2,4],[1,6],[5,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if x!=fa[x]:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(a,b):\n",
    "            x,y=find(a),find(b)\n",
    "            if x!=y:\n",
    "                fa[y]=x\n",
    "                size[x]+=size[y]\n",
    "        \n",
    "        fa={i:i for i in range(n)}\n",
    "        size=[1]*n\n",
    "\n",
    "        for a,b in edges:\n",
    "            union(a,b)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans+=n-size[find(i)]\n",
    "        return ans//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        fa = {i:i for i in range(n)}\n",
    "        def find(i):\n",
    "            if fa[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i] = find(fa[i])\n",
    "                return fa[i]\n",
    "        \n",
    "        for i, j in edges:\n",
    "            u = find(i)\n",
    "            v = find(j)\n",
    "            if u != v:\n",
    "                fa[v] = u\n",
    "\n",
    "        import collections\n",
    "        count = collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            count[find(i)] += 1\n",
    "\n",
    "        result = 0\n",
    "        for i in count.values():\n",
    "            result += (n-i)*i\n",
    "        \n",
    "        return result//2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf=UnionFind(n)\n",
    "        for x,y in edges:\n",
    "            uf.union(x,y)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            res+=n-uf.get_size(uf.find(i))\n",
    "        return res//2\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n:int):\n",
    "        # 负数即为根，其绝对值为包括根在内的节点数\n",
    "        self.parents=[-1]*n\n",
    "\n",
    "    def find(self,x:int)->int:\n",
    "        root=x\n",
    "        while(self.parents[root]>=0):\n",
    "            root=self.parents[root]\n",
    "        while(x!=root):\n",
    "            px=self.parents[x]\n",
    "            self.parents[x]=root\n",
    "            x=px\n",
    "        return root\n",
    "\n",
    "    def union(self,x:int,y:int):\n",
    "        rx=self.find(x)\n",
    "        ry=self.find(y)\n",
    "        if rx!=ry:\n",
    "            if self.parents[rx]<self.parents[ry]:\n",
    "                self.parents[rx]+=self.parents[ry]\n",
    "                self.parents[ry]=rx\n",
    "            else:\n",
    "                self.parents[ry]+=self.parents[rx]\n",
    "                self.parents[rx]=ry\n",
    "\n",
    "    def get_size(self,x:int) -> int:\n",
    "        return -self.parents[x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for x, y in edges:\n",
    "            uf.union(x, y)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += n - uf.getSize(uf.find(i))\n",
    "        return res // 2\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parents = [i for i in range(n)]\n",
    "        self.sizes = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parents[x] == x:\n",
    "            return x\n",
    "        else:\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "            return self.parents[x]\n",
    "\n",
    "    def union(self, x: int, y: int):\n",
    "        rx = self.find(x)\n",
    "        ry = self.find(y)\n",
    "        if rx != ry:\n",
    "            if self.sizes[rx] > self.sizes[ry]:\n",
    "                self.parents[ry] = rx\n",
    "                self.sizes[rx] += self.sizes[ry]\n",
    "            else:\n",
    "                self.parents[rx] = ry\n",
    "                self.sizes[ry] += self.sizes[rx]\n",
    "\n",
    "    def getSize(self, x: int) -> int:\n",
    "        return self.sizes[x]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        father = [_ for _ in range(n)]\n",
    "        size = [1 for _ in range(n)]\n",
    "        def find(x):\n",
    "            if father[x] == x:\n",
    "                return x\n",
    "            father[x] = find(father[x])\n",
    "            return father[x]\n",
    "        def merge(x,y):\n",
    "            fx = find(x)\n",
    "            fy = find(y)\n",
    "            if fx != fy:\n",
    "                if size[fx] > size[fy]:\n",
    "                    father[fy] = father[fx]\n",
    "                    size[fx] += size[fy]\n",
    "                else:\n",
    "                    father[fx] = father[fy]\n",
    "                    size[fy] += size[fx]\n",
    "            \n",
    "        for edge in edges:\n",
    "            merge(edge[0],edge[1])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += n - size[find(i)]\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        fa = [i for i in range(n)]\n",
    "        def find(x):\n",
    "            if x == fa[x]:\n",
    "                return x\n",
    "            return find(fa[x])\n",
    "        \n",
    "        def union(x,y,fa):\n",
    "            fx,fy = find(x),find(y)\n",
    "            if fx != fy:\n",
    "                fa[fy] = fx\n",
    "                \n",
    "        for s,e in edges:\n",
    "            union(s,e,fa)\n",
    "        for i in range(n):\n",
    "            fa[i] = find(i)\n",
    "        d1 = {}\n",
    "        for f in fa:\n",
    "            if f in d1:\n",
    "                d1[f] += 1\n",
    "            else:\n",
    "                d1[f] = 1\n",
    "        d2 = {}\n",
    "        for k in d1:\n",
    "            if d1[k] in d2:\n",
    "                d2[d1[k]] += 1\n",
    "            else:\n",
    "                d2[d1[k]] = 1\n",
    "        res = 0\n",
    "        for k1 in d2:\n",
    "            for k2 in d2:\n",
    "                if k1!=k2:\n",
    "                    res += (k1*k2*d2[k1]*d2[k2])\n",
    "        res = res//2\n",
    "        for k in d2:\n",
    "            res += ((d2[k]-1)*d2[k]//2*k**2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.fa = list(range(n))\n",
    "        self.du = [1]*n\n",
    "        def findf(a):\n",
    "            if self.fa[a] != a:\n",
    "                self.fa[a] = findf(self.fa[a])\n",
    "            return self.fa[a]\n",
    "\n",
    "        def union(a,b):\n",
    "            af = findf(a)\n",
    "            bf = findf(b)\n",
    "            if af == bf:\n",
    "                return\n",
    "            elif self.du[af]>self.du[bf]:\n",
    "                self.fa[bf] = af\n",
    "                self.du[af] += self.du[bf]\n",
    "            else:\n",
    "                self.fa[af] = bf\n",
    "                self.du[bf] += self.du[af]\n",
    "        \n",
    "        for i in edges:\n",
    "            union(*i)\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            if self.fa[i] == i:\n",
    "                ans += self.du[i]*s\n",
    "                s += self.du[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        nearby = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            nearby[u].add(v)\n",
    "            nearby[v].add(u)\n",
    "            \n",
    "        status = [0] * n\n",
    "        ret = n*(n-1)//2\n",
    "        for start in range(n):\n",
    "            if status[start] != 0:\n",
    "                continue\n",
    "            q = {start}\n",
    "            checked = set()\n",
    "            while q:\n",
    "                checked |= q\n",
    "                new_q = set()\n",
    "                for u in q:\n",
    "                    new_q |= nearby[u]\n",
    "                q = new_q - checked\n",
    "                \n",
    "            for x in checked:\n",
    "                status[x] = 1\n",
    "            cnt = len(checked)\n",
    "            ret -= cnt*(cnt-1)//2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        nearby = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            nearby[u].add(v)\n",
    "            nearby[v].add(u)\n",
    "\n",
    "        status = [0] * n\n",
    "        ret = n*(n-1)//2\n",
    "        for start in range(n):\n",
    "            if status[start] == 1:\n",
    "                continue\n",
    "            q = [start]\n",
    "            l = 0\n",
    "            status[start] = 1\n",
    "            while l < len(q):\n",
    "                r = len(q)\n",
    "                for i in range(l, r):\n",
    "                    for v in nearby[q[i]]:\n",
    "                        if status[v] == 1:\n",
    "                            continue\n",
    "                        status[v] = 1\n",
    "                        q.append(v)\n",
    "                l = r\n",
    "\n",
    "            cnt = len(q)\n",
    "            ret -= cnt*(cnt-1)//2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 题目等价于找无向图中的岛\n",
    "        # 并查集？\n",
    "        # 建图\n",
    "        d = defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            d[a].add(b)\n",
    "            d[b].add(a)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        visited = [False] * n  # 结点编号是连续的\n",
    "        for i in range(n):\n",
    "            # bfs\n",
    "            if not visited[i]:\n",
    "                cnt = 0\n",
    "                q = deque()\n",
    "                q.append(i)\n",
    "                while q:\n",
    "                    crt = q.popleft()\n",
    "                    if not visited[crt]:\n",
    "                        for node in d[crt]:\n",
    "                            q.append(node)\n",
    "                        visited[crt] = True\n",
    "                        cnt += 1\n",
    "                res += cnt*(n-cnt)\n",
    "        return res//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dic=dict()\n",
    "        for i in range(n):\n",
    "            dic[i]=set()\n",
    "        for i in edges:\n",
    "            s=dic.get(i[0],set())\n",
    "            s.add(i[1])\n",
    "            dic[i[0]]=s\n",
    "            s=dic.get(i[1],set())\n",
    "            s.add(i[0])\n",
    "            dic[i[1]]=s\n",
    "        last,c=0,0\n",
    "        while dic!=dict():\n",
    "            s=dic.popitem()\n",
    "            dic[s[0]]=s[1]\n",
    "            next={s[0]}\n",
    "            x=0\n",
    "            while next!=set():\n",
    "                now=next\n",
    "                next=set()\n",
    "                for i in now:\n",
    "                    for j in dic.get(i,set()):\n",
    "                        next.add(j)\n",
    "                        dic[j].discard(i)\n",
    "                        if dic[j]==set():\n",
    "                            del dic[j]\n",
    "                            x+=1\n",
    "                    if dic.get(i,None)!=None:\n",
    "                        del dic[i]\n",
    "                        x+=1\n",
    "            c+=last*x\n",
    "            last+=x\n",
    "        return c\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        used = set()\n",
    "        g = {}\n",
    "        for x, y in edges:\n",
    "            if x not in g:\n",
    "                g[x] = set()\n",
    "            if y not in g:\n",
    "                g[y] = set()\n",
    "            \n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        \n",
    "        res = n * (n - 1) / 2\n",
    "        for index in range(n):\n",
    "            if index not in used:\n",
    "                used.add(index)\n",
    "                q = [index]\n",
    "                l = 0\n",
    "                r = 1\n",
    "                while l < r:\n",
    "                    now = q[l]\n",
    "                    l += 1\n",
    "                    for next in g.get(now, set()):\n",
    "                        if next not in used:\n",
    "                            q.append(next)\n",
    "                            r += 1\n",
    "                            used.add(next)\n",
    "                \n",
    "                res -= r * (r - 1) / 2\n",
    "        \n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        # 先统计每个点走一步可到达的点的映射\n",
    "        dic = defaultdict(set)\n",
    "        for edge in edges:\n",
    "            dic[edge[0]].add(edge[1])\n",
    "            dic[edge[1]].add(edge[0])\n",
    "        # 对于已经访问过的节点，我们直接跳过\n",
    "        seen = set()\n",
    "        # 总点对数目\n",
    "        ans = n*(n-1)/2\n",
    "        for i in range(n):\n",
    "            # 若节点i还没见过，进去走走\n",
    "            if i not in seen:\n",
    "                # 当前节点i所组成的连通集\n",
    "                curcycle = set()\n",
    "                # 从节点i出发BFS\n",
    "                queue = deque([i])\n",
    "                while queue:\n",
    "                    cur = queue.popleft()\n",
    "                    dirc = dic[cur]\n",
    "                    for d in dirc:\n",
    "                        if d not in curcycle and d not in seen:\n",
    "                            curcycle.add(d)\n",
    "                            seen.add(d)\n",
    "                            queue.append(d)\n",
    "                # 用总点对减去当前联通集合的点对数目\n",
    "                ans -= (len(curcycle)-1)*len(curcycle)/2\n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        parents = [i for i in range(n)]\n",
    "        size = [1] * n\n",
    "        sz = 0\n",
    "        ans = 1\n",
    "        def union(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                parents[fx] = fy\n",
    "                size[fy] += size[fx]\n",
    "        def find(x):\n",
    "            if parents[x] != x:\n",
    "                parents[x] = find(parents[x])\n",
    "            return parents[x]\n",
    "        for x, y in edges:\n",
    "            union(x, y)\n",
    "        print(parents)\n",
    "        for i in range(n):\n",
    "            if parents[i] == i:\n",
    "                print(i)\n",
    "                print(size[i])\n",
    "                sz += 1\n",
    "                ans += (n - size[i]) * size[i]\n",
    "                \n",
    "\n",
    "        return (ans // 2) if sz > 1 else 0\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parents = [i for i in range(n)]\n",
    "        self.sizes = [1 for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parents[x] == x:\n",
    "            return x\n",
    "        else:\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "            return self.parents[x]    \n",
    "            \n",
    "    def union(self, x, y):\n",
    "        parent_x, parent_y = self.find(x), self.find(y)\n",
    "        size_x, size_y = self.sizes[x], self.sizes[y]\n",
    "        if parent_x==parent_y: return\n",
    "        if size_x > size_y:\n",
    "            self.parents[parent_y] = parent_x\n",
    "            self.sizes[parent_x] += self.sizes[parent_y]\n",
    "        else:\n",
    "            self.parents[parent_x] = parent_y\n",
    "            self.sizes[parent_y] += self.sizes[parent_x]\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        u = UnionFind(n)\n",
    "        for e in edges:\n",
    "            u.union(e[0], e[1])\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += n - u.sizes[u.find(i)]\n",
    "        return res // 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        d = {i:set() for i in range(n)}\n",
    "        for a, b in edges:\n",
    "            d[a].add(b)\n",
    "            d[b].add(a)\n",
    "        \n",
    "        total = set([i for i in range(n)])\n",
    "        parts = []\n",
    "\n",
    "        while total:\n",
    "            visit = set()\n",
    "            st = set([total.pop()])\n",
    "            while st:\n",
    "                new = set()\n",
    "                for p in st:\n",
    "                    new |= d[p]\n",
    "                visit |= st\n",
    "                new -= visit\n",
    "                st = new\n",
    "            parts.append(len(visit))\n",
    "            total -= visit\n",
    "        \n",
    "        ans = 0\n",
    "        t = 0\n",
    "        for p in parts:\n",
    "            t += p\n",
    "            ans += p*(n-t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for x, y in edges:\n",
    "            uf.union(x, y)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += n - uf.getSize(uf.find(i))\n",
    "        return res // 2\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parents = [i for i in range(n)]\n",
    "        self.sizes = [1] * n\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parents[x] == x:\n",
    "            return x\n",
    "        else:\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "            return self.parents[x]\n",
    "\n",
    "    def union(self, x: int, y: int):\n",
    "        rx = self.find(x)\n",
    "        ry = self.find(y)\n",
    "        if rx != ry:\n",
    "            if self.sizes[rx] > self.sizes[ry]:\n",
    "                self.parents[ry] = rx\n",
    "                self.sizes[rx] += self.sizes[ry]\n",
    "            else:\n",
    "                self.parents[rx] = ry\n",
    "                self.sizes[ry] += self.sizes[rx]\n",
    "\n",
    "    def getSize(self, x: int) -> int:\n",
    "        return self.sizes[x]\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \n",
    "        graph = defaultdict(set)\n",
    "        \n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "            \n",
    "        visited = [False for _ in range(n)]\n",
    "\n",
    "        cc = 0\n",
    "        cc2nodes = defaultdict(set)\n",
    "\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                cc += 1\n",
    "                \n",
    "                que = deque()\n",
    "                que.append(i)\n",
    "\n",
    "                while que:\n",
    "                    u = que.popleft()\n",
    "                    if u not in cc2nodes[cc]:\n",
    "                        cc2nodes[cc].add(u)\n",
    "                    \n",
    "                    for v in graph[u]:\n",
    "                        if not visited[v]:\n",
    "                            visited[v] = True\n",
    "                            que.append(v)\n",
    "\n",
    "        cnt = [len(nodes) for _, nodes in cc2nodes.items()]\n",
    "        m = len(cnt)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            res += cnt[i] * (n - cnt[i])\n",
    "\n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        d, l, visited = {i:set() for i in range(n)}, [], set()\n",
    "        for u, v in edges:\n",
    "            d[u].add(v)\n",
    "            d[v].add(u)\n",
    "        for k in d.keys():\n",
    "            if k not in visited:\n",
    "                l.append(set())\n",
    "                tmp = [k]\n",
    "                while tmp:\n",
    "                    x = tmp.pop()\n",
    "                    visited.add(x)\n",
    "                    l[-1].add(x)\n",
    "                    tmp += list(d[x]-visited)\n",
    "        return sum(len(x)*(n-len(x)) for x in l)//2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        arr = [i for i in range(n)]\n",
    "        def find(a:int):\n",
    "            if a == arr[a]:\n",
    "                return a\n",
    "            else:\n",
    "                boss = find(arr[a])\n",
    "                arr[a] = boss\n",
    "                return boss\n",
    "        def combine(a:int,b:int):\n",
    "            ba,bb = find(a),find(b)\n",
    "            if ba == bb:\n",
    "                return False\n",
    "            arr[ba] = bb\n",
    "            return True\n",
    "        for x,y in edges:\n",
    "            combine(x,y)\n",
    "        for i in range(n):\n",
    "            arr[i] = find(i)\n",
    "        ans = 0\n",
    "        c = Counter(arr)\n",
    "        for x in c:\n",
    "            ans += c[x]*(n - c[x])\n",
    "        return ans//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        def find(x):\n",
    "            if x == p[x]:\n",
    "                return x\n",
    "            p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            px, py = find(x), find(y)\n",
    "            if px != py:\n",
    "                p[px] = py\n",
    "\n",
    "        p = list(range(n))\n",
    "        for x, y in edges:\n",
    "            union(x, y)\n",
    "        for i in range(n):\n",
    "            find(i)\n",
    "        # print(p)\n",
    "        ans = 0\n",
    "        cnt = defaultdict(int)\n",
    "        for i in p:\n",
    "            cnt[i] += 1\n",
    "        # print(cnt)\n",
    "        ans = 0\n",
    "        for v in cnt.values():\n",
    "            ans += v * (n - v)\n",
    "        return ans // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "         # 查：寻找x的祖先节点\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        \n",
    "        # 并：将x的祖先节点挂到y的祖先节点上\n",
    "        def union(x, y):\n",
    "            parent[find(x)] = find(y)\n",
    "\n",
    "        parent = list(range(n))     # 初始化每个节点的祖先节点为其自身\n",
    "        for u, v in edges:\n",
    "            union(u, v)             # 并\n",
    "        \n",
    "        for i in range(n):          # 统一祖先节点：一个连通块压缩为一个点\n",
    "            parent[i] = find(i)\n",
    "        \n",
    "        vals = list(collections.Counter(parent).values())   # 每个连通块的大小\n",
    "        presum = list(accumulate(vals))                     # 连通块大小的前缀和\n",
    "        ans = 0\n",
    "        for i in range(len(vals)):\n",
    "            ans += vals[i] * (n - presum[i])                # 数学关系\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # bfs\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "            \n",
    "        visited = [False for _ in range(n)]\n",
    "        cc = 0\n",
    "        cc2nodes = defaultdict(set)\n",
    "\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                cc += 1\n",
    "                que = deque()\n",
    "                que.append(i)\n",
    "                while que:\n",
    "                    u = que.popleft()\n",
    "                    if u not in cc2nodes[cc]:\n",
    "                        cc2nodes[cc].add(u)\n",
    "                    \n",
    "                    for v in graph[u]:\n",
    "                        if not visited[v]:\n",
    "                            visited[v] = True\n",
    "                            que.append(v)\n",
    "\n",
    "        cnts = map(len, cc2nodes.values())\n",
    "        res = 0\n",
    "        for cnt in cnts:\n",
    "            res += cnt * (n - cnt)\n",
    "        \n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parent = [[i,{i}] for i in range(n)]\n",
    "        rank = [0]*n\n",
    "        def fid(x):\n",
    "            nonlocal parent,rank\n",
    "            if parent[x][0] != x:\n",
    "                parent[x][0],parent[x][1] = fid(parent[x][0])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            nonlocal parent,rank\n",
    "            root_x,v_x = fid(x)\n",
    "            root_y,v_y = fid(y)\n",
    "            if root_x == root_y:\n",
    "                return\n",
    "            if rank[root_x] < rank[root_y]:\n",
    "                v_x.update(v_y)\n",
    "                parent[root_x] = [root_y,v_x]\n",
    "            elif rank[root_x] > rank[root_y]:\n",
    "                v_y.update(v_x)\n",
    "                parent[root_y] = [root_x,v_y]\n",
    "            else:\n",
    "                v_y.update(v_x)\n",
    "                parent[root_y] = [root_x,v_y]\n",
    "                rank[root_x] += 1\n",
    "        visited = defaultdict(set)\n",
    "        for x,y in edges:\n",
    "            union(x,y)\n",
    "        for i in range(n):\n",
    "            root,v = fid(i)\n",
    "            visited[root].add(i)\n",
    "        ans = 0\n",
    "        for k,v in visited.items():\n",
    "            m = len(v)\n",
    "            ans += m*(n-m)\n",
    "            #print(f'查找{k} 与他连接的是{v},{m}')\n",
    "            \n",
    "        return 0 if ans == 0 else int(ans/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self, x):\n",
    "        if self.f[x] == x:\n",
    "            return x\n",
    "        else:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "            return self.f[x]\n",
    "    \n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        self.f = [0] * n\n",
    "        for i in range(n):\n",
    "            self.f[i] = i\n",
    "        \n",
    "        for edge in edges:\n",
    "            self.f[self.find(edge[0])] = self.find(edge[1])\n",
    "        \n",
    "        for i in range(n):\n",
    "            fa = self.find(i)\n",
    "            if fa not in dic:\n",
    "                dic.update({fa: 1})\n",
    "            else:\n",
    "                dic[fa] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            fa = self.find(i)\n",
    "            ans += (n-dic[fa])\n",
    "\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.f = [i for i in range(n)]\n",
    "\n",
    "    def find(self, x):\n",
    "        \"\"\" 找x的根结点 \"\"\"\n",
    "        self.f[x] = x if self.f[x] == x else self.find(self.f[x])   # 路径压缩\n",
    "        return self.f[x]\n",
    "    \n",
    "    def merge(self, x, y):\n",
    "        \"\"\" 合并x与y到同一个集合中 \"\"\"\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.f[root_x] = root_y  # 直接挂载根结点\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dsu = DSU(n)\n",
    "        for (i, j) in edges:\n",
    "            dsu.merge(i, j)\n",
    "        # 统计不同连通图的节点个数\n",
    "        root_dict = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            root_dict[dsu.find(i)] += 1\n",
    "        nums = list(root_dict.values())\n",
    "        # 计算点对个数\n",
    "        sums = sum(nums)\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            sums -= x\n",
    "            ans += x * sums\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for x , y in edges:\n",
    "            uf.union(x, y)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += n - uf.getR(uf.find(i))\n",
    "        return res // 2\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.p = [i for i in range(n)]\n",
    "        self.r = [1] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.p[x] == x:\n",
    "            return x \n",
    "        else:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "            return self.p[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rx = self.find(x)\n",
    "        ry = self.find(y)\n",
    "        if rx != ry:\n",
    "            if rx < ry:\n",
    "                self.p[rx] = ry\n",
    "                self.r[ry] += self.r[rx]\n",
    "            else:\n",
    "                self.p[ry] = rx\n",
    "                self.r[rx] += self.r[ry]\n",
    "    \n",
    "    def getR(self, x):\n",
    "        return self.r[x]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        parent = [i for i in range(n)]\n",
    "\n",
    "        def find(x):\n",
    "            if x == parent[x]:\n",
    "                return x\n",
    "            parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            parent[find(x)] = find(y)\n",
    "\n",
    "        for [u,v] in edges:\n",
    "            union(u,v)\n",
    "        \n",
    "        parCnt = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            parCnt[find(i)] += 1\n",
    "\n",
    "        ans, summ = 0, 0\n",
    "        for k in parCnt.keys():\n",
    "            ans += summ*parCnt[k]\n",
    "            summ += parCnt[k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        pa = [i for i in range(n)]\n",
    "        def find(x: int) -> int:\n",
    "            if x != pa[x]:\n",
    "                pa[x] = find(pa[x])\n",
    "            \n",
    "            return pa[x]\n",
    "        \n",
    "        def union(x: int, y: int) -> None:\n",
    "            r1, r2 = find(x), find(y)\n",
    "            if r1 != r2:\n",
    "                pa[r1] = r2\n",
    "        \n",
    "        for x, y in edges:\n",
    "            union(x, y)\n",
    "\n",
    "        for x in range(n):\n",
    "            find(x)\n",
    "        \n",
    "        cnt = Counter(pa).values()\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for num in cnt:\n",
    "            ans += num * s\n",
    "            s += num\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        parent = [i for i in range(n)]\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x: int, y: int) -> None:\n",
    "            x_p = find(x)\n",
    "            y_p = find(y)\n",
    "            if (x_p == y_p):\n",
    "                return None\n",
    "            parent[x_p] = y_p\n",
    "\n",
    "        for a, b in edges:\n",
    "            union(a, b)\n",
    "\n",
    "        cnt = Counter()\n",
    "        for o in range(n):\n",
    "            cnt[find(o)] += 1\n",
    "\n",
    "        ans = total = 0\n",
    "\n",
    "        for num in cnt.values():\n",
    "            ans += num * total\n",
    "            total += num\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parents = [i for i in range(n)]\n",
    "        self.sizes = [1]*n\n",
    "    def find(self, p):\n",
    "        if self.parents[p] != p:\n",
    "            self.parents[p] = self.find(self.parents[p])\n",
    "        return self.parents[p]\n",
    "    def union(self, p, q):\n",
    "        p_p = self.find(p)\n",
    "        p_q = self.find(q)\n",
    "        if p_p != p_q:\n",
    "            self.parents[p_p] = p_q\n",
    "            self.sizes[p_q] += self.sizes[p_p]\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for a, b in edges:\n",
    "            uf.union(a, b)\n",
    "        sizes = []\n",
    "        seen = set()\n",
    "        for node in range(n):\n",
    "            root = uf.find(node)\n",
    "            if root not in seen:\n",
    "                seen.add(root)\n",
    "                sizes.append(uf.sizes[root])\n",
    "        ans = 0\n",
    "        pre_sum = sizes[0]\n",
    "        for i in range(1, len(sizes)):\n",
    "            ans += sizes[i]*pre_sum\n",
    "            pre_sum += sizes[i]\n",
    "            \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for x, y in edges:\n",
    "            uf.union(x, y)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += n - uf.getSize(uf.find(i))\n",
    "        return res // 2\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.size = [1] * n\n",
    "        self.parents = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, x: int):\n",
    "        if self.parents[x] != x:\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "    \n",
    "    def union(self, x: int, y: int):\n",
    "        nx = self.find(x)\n",
    "        ny = self.find(y)\n",
    "        if nx != ny :\n",
    "            if self.parents[nx] > self.parents[ny]:\n",
    "                self.parents[ny] = nx\n",
    "                self.size[nx] += self.size[ny]\n",
    "            else:\n",
    "                self.parents[nx] = ny\n",
    "                self.size[ny] += self.size[nx]\n",
    "\n",
    "    def getSize(self, x: int):\n",
    "        return self.size[x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        fa = dict()\n",
    "        for x in range(n):\n",
    "            fa[x] = x\n",
    "        def find(x):\n",
    "            if x == fa[x]:\n",
    "                return x\n",
    "            else:\n",
    "                fa[x] = find(fa[x])\n",
    "                return fa[x]\n",
    "        def merge(x, y):\n",
    "            fa[find(x)] = find(y)\n",
    "        \n",
    "        for edge in edges:\n",
    "            merge(edge[0], edge[1])\n",
    "        \n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            d.setdefault(find(i), 0)\n",
    "            d[find(i)] += 1\n",
    "\n",
    "        items = []\n",
    "        for key, value in d.items():\n",
    "            items.append(value)\n",
    "        cnt = 0\n",
    "        for i in range(len(items)):\n",
    "            cnt += (items[i] * (n - items[i]))\n",
    "        return cnt // 2\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "        self.graph = []\n",
    "        self.visited = []\n",
    "\n",
    "    def dfs(self, x):\n",
    "        self.visited[x] = True\n",
    "        count = 1\n",
    "        for y in self.graph[x]:\n",
    "            if not self.visited[y]:\n",
    "                count += self.dfs(y)\n",
    "\n",
    "        return count\n",
    "\n",
    "\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        if(n * (n - 1) // 2 == len(edges)):\n",
    "            return 0\n",
    "\n",
    "        self.graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            self.graph[x].append(y)\n",
    "            self.graph[y].append(x)\n",
    "\n",
    "        self.visited = [False] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            if not self.visited[i]:\n",
    "                count = self.dfs(i)\n",
    "                self.res += count * (n - count)\n",
    "\n",
    "        return self.res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Graph:\n",
    "    def __init__(self, V):\n",
    "        self.V = V\n",
    "        self.graph = [[] for _ in range(V)]\n",
    "        self.vistied = [False] * V\n",
    "        self.count = 0\n",
    "    \n",
    "    def add_edge(self, u, v):\n",
    "        self.graph[u].append(v)\n",
    "        self.graph[v].append(u)\n",
    "\n",
    "    def DFS(self, src):\n",
    "        if not self.vistied[src]:\n",
    "            self.vistied[src] = 1\n",
    "            self.count += 1\n",
    "            for node in self.graph[src]:\n",
    "                if not self.vistied[node]:\n",
    "                    self.DFS(node)\n",
    "\n",
    "    def search_reachable(self):\n",
    "        ans = 0\n",
    "        for i in range(self.V):\n",
    "            self.count = 0\n",
    "            self.DFS(i)\n",
    "            ans += (self.V - self.count) * self.count\n",
    "        return ans // 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = Graph(n)\n",
    "        for edge in edges:\n",
    "            g.add_edge(*edge)\n",
    "        return g.search_reachable()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mark = []\n",
    "        self.graph = [[]]\n",
    "        self.n = 0\n",
    "\n",
    "    def dfs(self, x: int) -> int:\n",
    "        if self.mark[x]:\n",
    "            return 0\n",
    "        self.mark[x] = True\n",
    "        count = 1\n",
    "        for y in self.graph[x]:\n",
    "            if self.mark[y]:\n",
    "                continue\n",
    "            count += self.dfs(y)\n",
    "        return count\n",
    "\n",
    "    # 以示例二计算为例子\n",
    "    # [4 * (7 - 4) + 2 * (7 - 2) + 1 * (7 - 1)] // 2\n",
    "    # (12 + 10 + 6) // 2\n",
    "    # 28 // 2\n",
    "    # 14\n",
    "    def solve(self) -> int:\n",
    "        res = 0\n",
    "        for i in range(self.n):\n",
    "            count = self.dfs(i)\n",
    "            res += count * (self.n - count)\n",
    "        return res // 2\n",
    "\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.n = n\n",
    "        self.mark = [False for _ in range(n)]\n",
    "        self.graph = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            self.graph[x].append(y)\n",
    "            self.graph[y].append(x)\n",
    "\n",
    "        return self.solve()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # pic = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        # for edge in edges:\n",
    "        #     pic[edge[0]][edge[1]] = 1\n",
    "        #     pic[edge[1]][edge[0]] = 1\n",
    "        # node_list = [i for i in range(n)]\n",
    "        # is_used = [0 for _ in range(n)]\n",
    "        # def find_node(start_node):\n",
    "        #     nonlocal pic\n",
    "        #     nonlocal node_list\n",
    "        #     q = [start_node]\n",
    "        #     have_visited = set([start_node])\n",
    "        #     count = 0\n",
    "        #     while q:\n",
    "        #         count += 1\n",
    "        #         cur_node = q.pop(0)\n",
    "        #         for i in range(n):\n",
    "        #             if pic[cur_node][i] == 1 and i not in have_visited:\n",
    "        #                 have_visited.add(i)\n",
    "        #                 q.append(i)\n",
    "        #                 is_used[i] = 1\n",
    "        #     return count\n",
    "\n",
    "        # res = []\n",
    "        # index = 0\n",
    "        # while not all(is_used):\n",
    "        #     if is_used[index]:\n",
    "        #         index += 1\n",
    "        #         continue\n",
    "        #     cur_node = node_list[index]\n",
    "        #     is_used[index] = 1\n",
    "        #     index += 1\n",
    "        #     res.append(find_node(cur_node))\n",
    "        # result = 0\n",
    "        # for i in res:\n",
    "        #     result += ((n-i) * i)\n",
    "        # return result//2\n",
    "\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x) \n",
    "\n",
    "        visited = [False] * n\n",
    "        def dfs(x: int) -> int:\n",
    "            visited[x] = True \n",
    "            count = 1\n",
    "            for y in graph[x]:\n",
    "                if not visited[y]:\n",
    "                    count += dfs(y)\n",
    "            return count\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]: \n",
    "                count = dfs(i)\n",
    "                res += count * (n - count)\n",
    "        return res // 2\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x) \n",
    "\n",
    "        visited = [False] * n\n",
    "        def dfs(x: int) -> int:\n",
    "            visited[x] = True \n",
    "            count = 1\n",
    "            for y in graph[x]:\n",
    "                if not visited[y]:\n",
    "                    count += dfs(y)\n",
    "            return count\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]: \n",
    "                count = dfs(i)\n",
    "                res += count * (n - count)\n",
    "        return res // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph=[]\n",
    "        for i in range(n):\n",
    "            graph.append([])\n",
    "        \n",
    "        for x,y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        def dfs(x) -> int:\n",
    "            visited.add(x)\n",
    "            count = 1\n",
    "            for next in graph[x]:\n",
    "                if next not in visited:\n",
    "                    count += dfs(next)\n",
    "            return count\n",
    "\n",
    "        visited = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                count = dfs(i)\n",
    "                ans += count * (n - count)\n",
    "        return ans // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n, edges):\n",
    "        m = defaultdict(list)\n",
    "        for x, y, in edges:\n",
    "            m[x].append(y)\n",
    "            m[y].append(x)\n",
    "\n",
    "        len_path = 0\n",
    "        rec_path = [False] * n\n",
    "\n",
    "        def recur(node):\n",
    "            if rec_path[node]:\n",
    "                return\n",
    "\n",
    "            nonlocal len_path\n",
    "            len_path += 1\n",
    "            rec_path[node] = True\n",
    "            for nod in m[node]:\n",
    "                recur(nod)\n",
    "            return\n",
    "\n",
    "        ret = 0\n",
    "        pre = 0\n",
    "        for node in range(n):\n",
    "            len_path = 0\n",
    "            recur(node)\n",
    "            if len_path:\n",
    "               ret += pre * len_path\n",
    "               pre += len_path\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        vis = [0] *n\n",
    "        dt = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            dt[a].append(b)\n",
    "            dt[b].append(a)\n",
    "\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal cnt\n",
    "            vis[node] = 1\n",
    "            cnt += 1\n",
    "            for ch in dt[node]:\n",
    "                if not vis[ch]:\n",
    "                    dfs(ch)\n",
    "        tmp = []\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                cnt = 0\n",
    "                dfs(i)\n",
    "                tmp.append(cnt)\n",
    "        # print(tmp)\n",
    "        res = 0\n",
    "        if len(tmp) == 1 :\n",
    "            return 0\n",
    "        m = len(tmp)\n",
    "        for i in range(m):\n",
    "            res += (n - tmp[i]) * tmp[i]\n",
    "        return res //2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        visited = [False for i in range(n)]\n",
    "        edge_dict = defaultdict(list)\n",
    "        for item in edges:\n",
    "            edge_dict[item[0]].append(item[1])\n",
    "            edge_dict[item[1]].append(item[0])\n",
    "        # print(edge_dict)\n",
    "        def dfs(node,visited):\n",
    "            count = 1\n",
    "            visited[node] = True\n",
    "            for next_node in edge_dict[node]:\n",
    "                if not visited[next_node]:\n",
    "                    count += dfs(next_node,visited)\n",
    "            return count\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                count = dfs(i,visited)\n",
    "                # disjoint_number.append(count)\n",
    "                res += count*(n-count)\n",
    "        return res//2\n",
    "                # print(i,s)\n",
    "        res = 0\n",
    "        # print(disjoint_number)\n",
    "        for i in range(len(disjoint_number)):\n",
    "            for j in range(i+1,len(disjoint_number)):\n",
    "                res += disjoint_number[i]*disjoint_number[j]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''题目转化成：求联通区域及其节点个数, 求图的连通区域可以用DFS'''\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.edges_dict = {}\n",
    "        self.traverse = set()\n",
    "\n",
    "    # return combine node num\n",
    "    def dfs(self, cur_n):\n",
    "        node_num = 1\n",
    "        self.traverse.add(cur_n)\n",
    "        if cur_n in self.edges_dict:\n",
    "            for n in self.edges_dict[cur_n]:\n",
    "                if n not in self.traverse:\n",
    "                    node_num += self.dfs(n)\n",
    "        return node_num\n",
    "                    \n",
    "    def countPairs(self, n , edges):\n",
    "        \n",
    "        res = 0\n",
    "        combine = []\n",
    "        # init edge dict\n",
    "        for edge in edges:\n",
    "            n1, n2 = edge\n",
    "            if n1 not in self.edges_dict:\n",
    "                self.edges_dict[n1] = []\n",
    "            if n2 not in self.edges_dict:\n",
    "                self.edges_dict[n2] = []\n",
    "            self.edges_dict[n1].append(n2)\n",
    "            self.edges_dict[n2].append(n1)\n",
    "        \n",
    "        for cur_n in range(0, n):\n",
    "            # 同连通区域的不遍历\n",
    "            if cur_n in self.traverse:\n",
    "                continue\n",
    "            node_num = self.dfs(cur_n)\n",
    "            combine.append(node_num)\n",
    "        \n",
    "        for e in combine:\n",
    "            res += e * (n - e)/2\n",
    "            \n",
    "        return int(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        used = set()\n",
    "        dic = defaultdict(list)\n",
    "        res = 0\n",
    "        for a, b in edges:\n",
    "            dic[a].append(b)\n",
    "            dic[b].append(a)\n",
    "\n",
    "        def dfs(i):\n",
    "            count = 1\n",
    "            used.add(i)\n",
    "            for j in dic[i]:\n",
    "                if j not in used:\n",
    "                    count += dfs(j)\n",
    "            return count\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in used:\n",
    "                count = dfs(i)\n",
    "                res += count*(n-count)\n",
    "        return res//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \n",
    "        g = [[] for i in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        pa = dict()\n",
    "        def find(x):\n",
    "            fx = pa.get(x, x)\n",
    "            return x if fx == x else find(fx)\n",
    "\n",
    "        visted = [0] * n\n",
    "        def dfs(u):\n",
    "            visted[u] = 1\n",
    "            for v in g[u]:\n",
    "                if visted[v]: continue\n",
    "                fu, fv = map(find, (u, v))\n",
    "                pa[fv] = fu\n",
    "\n",
    "                dfs(v)\n",
    "\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        \n",
    "        res = dict()\n",
    "        for i in range(n):\n",
    "            res[find(i)] = res.get(find(i), 0) + 1\n",
    "\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for v in res.values():\n",
    "            ans += v * s\n",
    "            s += v\n",
    "        return 0 if len(res) == 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def dfs(node, visited):\n",
    "        # 深度优先搜索遍历图的辅助函数\n",
    "            if node in visited:\n",
    "                return\n",
    "            visited.add(node)\n",
    "            for neighbor in graph[node]:\n",
    "                dfs(neighbor, visited)\n",
    "\n",
    "    # 步骤1: 根据边创建图的表示\n",
    "        graph = {i: [] for i in range(n)}  # 使用字典构造图，方便后续的添加操作\n",
    "        for edge in edges:\n",
    "            a, b = edge\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)  # 无向图，需要添加双向的边\n",
    "\n",
    "        # 步骤2: 使用DFS找出所有连通分量\n",
    "        components = []  # 用于存储每个连通分量中节点的列表\n",
    "        visited_global = set()  # 存储所有访问过的节点，避免重复遍历\n",
    "        for i in range(n):\n",
    "            if i not in visited_global:\n",
    "                visited = set()  # 针对每个连通分量单独记录访问过的节点\n",
    "                dfs(i, visited)\n",
    "                components.append(visited)\n",
    "                visited_global.update(visited)  # 更新全局访问记录\n",
    "\n",
    "        # 步骤3: 计算不连通的点对数量\n",
    "        result = 0\n",
    "        for comp in components:\n",
    "            # 对于每个连通分量，计算其外部的不连通点对\n",
    "            outer_points = n - len(comp)\n",
    "            result += len(comp) * outer_points  # 连通分量内的每个点都与外部的每个点不连通\n",
    "\n",
    "        result //= 2  # 每对点都计算了两次（一次来自每个点），所以需要除以2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        neigh={i:[] for i in range(n)}\n",
    "        for e in edges:\n",
    "            neigh[e[0]].append(e[1])\n",
    "            neigh[e[1]].append(e[0])\n",
    "        visited=set()\n",
    "        partlist=[]\n",
    "        def dfs(nownode):\n",
    "            if nownode in visited:\n",
    "                return 0\n",
    "            ans=1\n",
    "            visited.add(nownode)\n",
    "            for node in neigh[nownode]:\n",
    "                ans+=dfs(node)\n",
    "            return ans\n",
    "\n",
    "        partlist.append(dfs(0))\n",
    "        while len(visited)<n:\n",
    "            for i in range(n):\n",
    "                if not i in visited:\n",
    "                    partlist.append(dfs(i))\n",
    "\n",
    "\n",
    "        if len(partlist)==1:\n",
    "            return 0\n",
    "        else:\n",
    "            ans=0\n",
    "            for i in partlist:\n",
    "                    ans+=i*(n-i)\n",
    "            return ans // 2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        set1=[set() for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            set1[x].add(y)\n",
    "            set1[y].add(x)\n",
    "        size=0\n",
    "        visted=[True]*n\n",
    "        def dfs(a:int):\n",
    "            visted[a]=False\n",
    "            nonlocal size \n",
    "            size +=1\n",
    "            for i in set1[a]:\n",
    "                if visted[i]:\n",
    "                    dfs(i)\n",
    "        res=0\n",
    "        total=0\n",
    "        for i in range(n):\n",
    "            if visted[i]:\n",
    "                dfs(i)\n",
    "                res+=total*size\n",
    "                total+=size\n",
    "                size=0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        linjie=[set() for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            linjie[x].add(y)\n",
    "            linjie[y].add(x)\n",
    "        def dfs(i):\n",
    "            temp=0\n",
    "            for x in linjie[i]:\n",
    "                \n",
    "                if not visited[x]:\n",
    "                    visited[x]=True\n",
    "                    temp+=dfs(x)\n",
    "            return 1+temp\n",
    "        visited=[False for _ in range(n)]\n",
    "        areaList = []\n",
    "        for i in range(n):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            visited[i] = True\n",
    "            areaList.append(dfs(i))\n",
    "        ans=0\n",
    "        for x in areaList:\n",
    "            ans+=x*(n-x)\n",
    "            n-=x\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, num):\n",
    "        self.num = num\n",
    "        self.nexts = []\n",
    "        self.visit = False\n",
    "        \n",
    "    \n",
    "    def add_next(self, node):\n",
    "        self.nexts.append(node)\n",
    "\n",
    "\n",
    "    def get_size(self):\n",
    "        self.visit = True\n",
    "        total_size = 1\n",
    "        for next_node in self.nexts:\n",
    "            if next_node.visit:\n",
    "                continue\n",
    "            total_size += next_node.get_size()\n",
    "        return total_size\n",
    "            \n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        nodes = []\n",
    "        for i in range(n):\n",
    "            nodes.append(Node(i))\n",
    "\n",
    "        for [i, j] in edges:\n",
    "            nodes[i].add_next(nodes[j])\n",
    "            nodes[j].add_next(nodes[i])\n",
    "\n",
    "        total_nodes = n * (n-1) \n",
    "        for i in range(n):\n",
    "            start_node = nodes[i]\n",
    "            if start_node.visit:\n",
    "                continue\n",
    "            size = start_node.get_size()\n",
    "            total_nodes -= size * (size - 1)\n",
    "        \n",
    "        return total_nodes // 2\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import deepcopy\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dic = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            dic[a].add(b)\n",
    "            dic[b].add(a)\n",
    "        \n",
    "        visited = [0] * n\n",
    "        def dfs(cur_node):\n",
    "            visited[cur_node] = 1\n",
    "            count = 1\n",
    "            for child in dic[cur_node]:\n",
    "                if not visited[child]:  \n",
    "                    count += dfs(child)\n",
    "            return count\n",
    "\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                count = dfs(i)\n",
    "                res += count * (n - count)\n",
    "\n",
    "        return res // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        info_dict=dict()\n",
    "        # 先把当前遍历一遍，存储了每个节点的相邻节点\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i][0] not in info_dict:\n",
    "                info_dict[edges[i][0]]=set()\n",
    "                info_dict[edges[i][0]].add(edges[i][1])\n",
    "            else:\n",
    "                info_dict[edges[i][0]].add(edges[i][1])\n",
    "            \n",
    "            if edges[i][1] not in info_dict:\n",
    "                info_dict[edges[i][1]]=set()\n",
    "                info_dict[edges[i][1]].add(edges[i][0])\n",
    "            else:\n",
    "                info_dict[edges[i][1]].add(edges[i][0])\n",
    "        \n",
    "\n",
    "        # 为了练习自己的思维，使用深度优先遍历求每个节点所能访问的所有节点的 个数\n",
    "        def depth_reach_node(node):\n",
    "            result_set=set()\n",
    "            def recur(node):\n",
    "                result_set.add(node)\n",
    "                for item in info_dict[node]:\n",
    "                    if item not in result_set:\n",
    "                        recur(item)\n",
    "            recur(node)\n",
    "            return result_set      \n",
    "\n",
    "        vis_list=[False]*n\n",
    "        for i in range(n):\n",
    "            if i in info_dict:\n",
    "                if not vis_list[i]:\n",
    "                    info_dict[i]=depth_reach_node(i)\n",
    "                    for item in info_dict[i]:\n",
    "                        vis_list[item]=True\n",
    "                    vis_list[i]=False\n",
    "                # print(\"i:\", i, \"vis_list:\", vis_list)\n",
    "        \n",
    "        # 在上面一段代码中，故意将已计算出所有联通的点设置为False\n",
    "        total_sum=0\n",
    "        for i in range(n):\n",
    "            if not vis_list[i]:\n",
    "                # vis_list[i]为False有两种可能，要么是孤立节点，要么是计算好的所有联通的点\n",
    "                if i not in info_dict:\n",
    "                    total_sum+=(n-1)\n",
    "                else:\n",
    "                    total_sum+=(n-len(info_dict[i]))*len(info_dict[i])\n",
    "        return total_sum//2\n",
    "        \n",
    "        # # 针对每个节点进行层次遍历，这样就能获得每个节点的能访问的所有节点了\n",
    "        # vis_list=[False]*n\n",
    "        # for i in range(n):\n",
    "        #     # 在info_dict里\n",
    "        #     if i in info_dict:\n",
    "        #         if not vis_list[i]:\n",
    "        #             temp_list=list(info_dict[i])\n",
    "        #             while len(temp_list):\n",
    "        #                 head_node=temp_list.pop(0)\n",
    "        #                 temp_set=info_dict[head_node]\n",
    "        #                 for item in temp_set:\n",
    "        #                     if item!=i and item not in info_dict[i]:\n",
    "        #                         temp_list.append(item)\n",
    "        #                         info_dict[i].add(item)\n",
    "        #             info_dict[i].add(i)\n",
    "        #             for item in info_dict[i]:\n",
    "        #                 info_dict[item]=info_dict[i]\n",
    "        #                 vis_list[item]=True\n",
    "\n",
    "\n",
    "        # # 计算每个节点到达不了的节点个数，所有节点加起来后除以2（因为到达不了的节点重复了2遍）\n",
    "        # total_sum=0\n",
    "        # for i in range(n):\n",
    "        #     if i in info_dict:\n",
    "        #         total_sum+=(n-len(info_dict[i]))\n",
    "        #     else:\n",
    "        #         total_sum+=(n-1)\n",
    "        # return int(total_sum/2)\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        \n",
    "        def dfs(node, seen):\n",
    "            seen.add(node)\n",
    "            for n in g[node]:\n",
    "                if n not in seen:\n",
    "                    dfs(n, seen)\n",
    "        \n",
    "        ans = n * n\n",
    "        visited = set()\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                prev = len(visited)\n",
    "                dfs(i, visited)\n",
    "                gn = len(visited) - prev\n",
    "                ans -= gn * gn\n",
    "        \n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            adj[u].add(v)\n",
    "            adj[v].add(u)\n",
    "        nodes = set(range(n))\n",
    "        def dfs(curr):\n",
    "            nonlocal cnt\n",
    "            if curr not in nodes:\n",
    "                return\n",
    "            nodes.remove(curr)\n",
    "            cnt += 1\n",
    "            for next in adj[curr]:\n",
    "                dfs(next)\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        independent = 0\n",
    "        while len(nodes) > 0:\n",
    "            cnt = 0\n",
    "            dfs(next(iter(nodes)))\n",
    "            ans += s * cnt\n",
    "            s += cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            adj[u].add(v)\n",
    "            adj[v].add(u)\n",
    "        nodes = set(range(n))\n",
    "        def dfs(curr):\n",
    "            nonlocal cnt\n",
    "            cnt = 1\n",
    "            for next in adj[curr]:\n",
    "                if next in nodes:\n",
    "                    nodes.remove(next)\n",
    "                    cnt += dfs(next)\n",
    "            return cnt\n",
    "        ans = 0\n",
    "        while len(nodes) > 0:\n",
    "            curr = next(iter(nodes))\n",
    "            nodes.remove(curr)\n",
    "            cnt = dfs(curr)\n",
    "            ans += cnt * (n-cnt)\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \n",
    "        # parts = defaultdict(set)\n",
    "        visited = [False for i in range(n)]\n",
    "        edge_dic = defaultdict(list)\n",
    "        for s, e in edges:\n",
    "            edge_dic[s].append(e)\n",
    "            edge_dic[e].append(s)\n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            visited[node] = True\n",
    "            # parts[root].add(node)\n",
    "            cnt = 1\n",
    "            for n in edge_dic[node]:\n",
    "                if not visited[n]:\n",
    "\n",
    "                    # parts[root].add(n)\n",
    "                    cnt += dfs(n)\n",
    "            return cnt\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                cnt = dfs(i)\n",
    "                res += cnt * (n - cnt)\n",
    "        return res // 2\n",
    "        '''\n",
    "        p = [len(parts[k]) for k in parts]\n",
    "        if len(p) == 1:\n",
    "            return 0\n",
    "        res = [p[i] * p[j] for i in range(len(p)) for j in range(i + 1, len(p))]\n",
    "        # print(res)\n",
    "        '''\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g, v = defaultdict(list), defaultdict(bool)\n",
    "        for i, j in edges:\n",
    "            g[i].append(j) or g[j].append(i)\n",
    "\n",
    "        def dfs(i):\n",
    "            if not v[i]:\n",
    "                v[i] = True\n",
    "                return 1 + sum(map(dfs, g[i]))\n",
    "            return 0\n",
    "        return sum((x := dfs(i)) * (n-x) for i in range(n)) >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "        visited = [False] * n\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            count = 1\n",
    "            visited[x] = True\n",
    "            for i in graph[x]:\n",
    "                if not visited[i]:\n",
    "                    count += dfs(i)\n",
    "            return count\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                now_node_num = dfs(i)\n",
    "                res += (n-now_node_num)*now_node_num\n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \n",
    "        # parts = defaultdict(set)\n",
    "        visited = [False for i in range(n)]\n",
    "        edge_dic = defaultdict(list)\n",
    "        for s, e in edges:\n",
    "            edge_dic[s].append(e)\n",
    "            edge_dic[e].append(s)\n",
    "        @cache\n",
    "        def dfs(node, root):\n",
    "            visited[node] = True\n",
    "            # parts[root].add(node)\n",
    "            cnt = 1\n",
    "            for n in edge_dic[node]:\n",
    "                if not visited[n]:\n",
    "\n",
    "                    # parts[root].add(n)\n",
    "                    cnt += dfs(n, root)\n",
    "            return cnt\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                cnt = dfs(i, i)\n",
    "                res += cnt * (n - cnt)\n",
    "        return res // 2\n",
    "        '''\n",
    "        p = [len(parts[k]) for k in parts]\n",
    "        if len(p) == 1:\n",
    "            return 0\n",
    "        res = [p[i] * p[j] for i in range(len(p)) for j in range(i + 1, len(p))]\n",
    "        # print(res)\n",
    "        '''\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    next = None\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        u = [Solution() for _ in range(n)]\n",
    "        for x in u:\n",
    "            x.next = None\n",
    "        def join(x, y):\n",
    "            if x.next:\n",
    "                x.next = join(x.next, y)\n",
    "                return x.next\n",
    "            elif y.next:\n",
    "                y.next = join(x, y.next)\n",
    "                return y.next\n",
    "            elif x != y:\n",
    "                x.next = y\n",
    "            return y\n",
    "        for a, b in edges:\n",
    "            join(u[a], u[b])\n",
    "        Σx = ans = 0\n",
    "        for x in Counter(join(a, a) for a in u).values():\n",
    "            Σx += x\n",
    "            ans -= x * x\n",
    "        return (ans + Σx * Σx) // 2  # ½((Σx)² − Σx²)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class myUF:\n",
    "    def __init__(self, n):\n",
    "        self.m1 = {}\n",
    "        for i in range(n):\n",
    "            self.m1[i] = i\n",
    "\n",
    "    def findP(self, x):\n",
    "        if self.m1[x] == x:\n",
    "            return x\n",
    "        res = self.m1[x]\n",
    "        res2  =self.findP(res)\n",
    "        self.m1[x] = res2\n",
    "        return res2\n",
    "\n",
    "    def uf(self,a,b):\n",
    "        pa = self.findP(a)\n",
    "        pb = self.findP(b)\n",
    "        if pa == pb:\n",
    "            return\n",
    "        self.m1[pa] = pb\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def findPQuick(self, x):\n",
    "        if self.m1[x] == x:\n",
    "            return x\n",
    "        res = self.m1[x]\n",
    "        return self.findPQuick(res)\n",
    "\n",
    "\n",
    "    def getGrp(self):\n",
    "        ret = {}\n",
    "        for i in self.m1:\n",
    "            res1 = self.findPQuick(i)\n",
    "            if res1 not in ret:\n",
    "                ret[res1] = [i]\n",
    "            else:\n",
    "                ret[res1].append(i)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]\n",
    "        :param n:\n",
    "        :param edges:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        uf1 = myUF(n)\n",
    "\n",
    "        for i in edges:\n",
    "            if i[0] < i[1]:\n",
    "                uf1.uf(i[0], i[1])\n",
    "            else:\n",
    "                uf1.uf(i[1], i[0])\n",
    "        q1 = uf1.getGrp()\n",
    "        cnt = 0\n",
    "\n",
    "\n",
    "        qq = []\n",
    "        m1  = {}\n",
    "        for i in q1:\n",
    "            qq.append(len(q1[i]))\n",
    "\n",
    "        dp = {}\n",
    "        cache = 0\n",
    "        c1 = 0\n",
    "        dp[-1] = 0\n",
    "        for i in qq:\n",
    "            cache += i\n",
    "            dp[c1] = cache\n",
    "            c1 += 1\n",
    "\n",
    "        if len(dp) == 2:\n",
    "            return 0\n",
    "        cnt = 0\n",
    "        for (k, v) in enumerate(qq):\n",
    "            toadd = dp[len(qq)-1] - dp[k]\n",
    "            todd2 = v * toadd\n",
    "            cnt += todd2\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "6\n",
    "[[0,1],[2,3],[4,5]]\n",
    "\"\"\"\n",
    "a = Solution()\n",
    "print(a.countPairs( n = 6, edges = [[0,1],[2,3],[4,5]]  ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPairs(self, n: int, edges: List[List[int]]) -> int:\n",
    "        arr = [[] for _ in range(n)]\n",
    "        for i,j in edges:\n",
    "            arr[i].append(j)\n",
    "            arr[j].append(i)\n",
    "        vis = [0]*n\n",
    "        def dfs(i):\n",
    "            if vis[i]:\n",
    "                return 0\n",
    "            vis[i] = 1\n",
    "            return 1+sum(dfs(j) for j in arr[i])\n",
    "        ans = 0\n",
    "        # for i in range(n):\n",
    "        #     vis = [False]*n\n",
    "        #     ans += (dfs(i)-1)\n",
    "        s = 0\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            t = dfs(i)\n",
    "            ans +=(n-t)*t\n",
    "        return ans//2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
